package InterfaceOffer;

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}


public class TencentSolution1 {
    public static ListNode solve(ListNode S) {
        // 首先建环
        ListNode start = S; // 记录建环前的初始位置
        ListNode index = S; // 用于遍历的指针
        int count = 0; // 用于记录一共有多少个值
        // 建环遍历的同时，寻找最小值，并记录指向最小值的指针
        int min = Integer.MAX_VALUE;
        ListNode minP;
        while (index.next != null) {
            if (index.val < min) {
                min = index.val;
                minP = index;
            }
            count++;
            index = index.next;
        }
        index.next = start; // 建环完毕
        // 然后寻找最小值的个数,并分别记录他们的起始位置
        index = start;
        List<ListNode> list = new ArrayList<>();
        while (index.next != S) {
            if (index.val == min) {
                ListNode node = index;
                list.add(node);
            }
            index = index.next;
        }

        ListNode[] listNodes = new ListNode[list.size()];
        //分别将这些指针，换成字符串，通过字符串来比较大小
        String[] arr = new String[list.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = "";
        }
        for (int i = 0; i < arr.length; i++) {
            ListNode node = list.remove(0);
            listNodes[i] = node;
            ListNode ind = node;
            while (ind.next != node) {
                arr[i] = arr[i] + ind.val;
                ind = ind.next;
            }
        }
        //找到arr里最小的那个
        String minstr = arr[0];
        int minindx = 0;
        for (int i = 1; i < arr.length; i++) {
            if (minstr.compareTo(arr[i]) > 0) {
                minstr = arr[i];
                minindx = i;
            }
        }
        // 断环
        ListNode finalNode = listNodes[minindx];
        while (finalNode.next != listNodes[minindx]) {
            finalNode = finalNode.next;
        }
        finalNode.next = null;
        return listNodes[minindx];
    }

    // 打印链表的方法
    public static void print(ListNode node) {
        while (node.next != null) {
            System.out.print(node.val + ",");
            node = node.next;
        }
        System.out.println(node.val);
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(2,new ListNode(2,new ListNode(2,new ListNode(2,new ListNode(5,null)))));
        print(solve(node));
    }


}
